// 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

function countSubstrings(s: string): number {
    if(s.length < 1){
        return 0;
    }
    const dp:boolean[][] = [];
    let count:number = 0;
    for(let i = 0;i<s.length;i++){// 初始化dp矩阵
        dp.push(new Array(s.length).fill(false));
    }
    for(let i = 0;i<s.length;i++){
        for(let j = 0;j<=i;j++){
            if(i === j){// 只有一个字符
                count++;
                dp[i][j] = true
            }else if(i - j <= 2 && s[i] === s[j]){// 只有两个字符且相等
                count++;
                dp[i][j] = true;
            }else if(i - j > 2 && s[j] === s[i] && dp[i-1][j+1] == true){// 状态转移方程
                count++;
                dp[i][j] = true;
            }
        }
    }
    return count;
};

// 这道题最直观的解法是使用破解算法，时间复杂度是On3，
// 包含字符串的遍历、字符串子串的遍历、回文串的判断，空间复杂度为O1，可以自行考虑实现
// 这里提到的是使用动态规划算法的解法，首先声明一个dp矩阵
// 我们使用dp[i][j]来表示字符串 s.slice(i,j+1) 是不是回文串。
// 这么思考的原因是一个字符串是回文串，要求它的首尾字符相同，
// 并且它的去除首尾的剩余子串也必须是一个回文串，而这个剩余子串是否是回文串又构成了一个子问题
// 即我们根据子串是回文串可以推断出父串，这是满足动态规划算法要求的
// 接下来我们遍历原字符串，一遍填表一边计数，dp[i][j]是回文串的要求如下：
// 1、i === j，即它是一个单独的字符，则必是回文串
// 2、由两个字符组成，且这两个字符是相等的。
// 3、由多于 2 个字符组成，首尾字符相同，且剩余子串是一个回文串。（状态转移方程）
// 根据上述的规则我们就可以写出时间复杂度On2的代码。

